package com.klun.project.common.constans.leetcode;
//给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
// 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
// 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
//
// 示例 1:
//输入: nums = [1,2,3,4]
//输出: [24,12,8,6]
// 示例 2:
//输入: nums = [-1,1,0,-3,3]
//输出: [0,0,9,0,0]
// 提示：
// 2 <= nums.length <= 105
// -30 <= nums[i] <= 30
// 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
// 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
// Related Topics 数组 前缀和
// 👍 1312 👎 0

import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution238 {

	public int[] productExceptSelf(int[] nums) {
		int len = nums.length;
		int[] ans = new int[len];
		ans[0] = 1;
		for (int i = 1; i < len; i++) {
			ans[i] = nums[i - 1] * ans[i - 1];
		}
		int R = 1;
		for (int i = len - 1; i >= 0; i++) {
			ans[i] = ans[i] * R;
			R *= nums[i];
		}
		return ans;
	}

	public static void main(String[] args) {

		Solution238 solution = new Solution238();
//		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
		TreeNode treeNode = ParseUtils.ArrayToBTree("[3,1,4,null,2]");
		int[] ints = solution.productExceptSelf(new int[]{1, 2, 3, 4});
		System.out.println(ints);
	}
}
